import java.util.*;


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}


public class Test_9_12 {

    //102. 二叉树的层序遍历
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        //自低向上用队列遍历结点，用栈存储每层的结点
        //用两个队列轮流存储每层的结点，完成一层遍历后，把那一层的结点存入一个栈中.
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) return ret;

        Queue<TreeNode> queue1 = new LinkedList<>();
        Queue<TreeNode> queue2 = new LinkedList<>();
        Stack<List<Integer>> stack = new Stack<>();
        queue1.offer(root);

        while(!queue1.isEmpty() || !queue2.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            if(!queue1.isEmpty()) {
                while(!queue1.isEmpty()) {
                    TreeNode front = queue1.poll();
                    list.add(front.val);
                    if(front.left != null) queue2.offer(front.left);
                    if(front.right != null) queue2.offer(front.right);
                }
            }else {
                while(!queue2.isEmpty()) {
                    TreeNode front = queue2.poll();
                    list.add(front.val);
                    if(front.left != null) queue1.offer(front.left);
                    if(front.right != null) queue1.offer(front.right);
                }
            }
            stack.push(list);
        }
        while(!stack.empty()) {
            ret.add(stack.pop());
        }
        return ret;
    }



    //106. 从中序与后序遍历序列构造二叉树
    public int postIndex;
    public TreeNode buildTree1(int[] inorder, int[] postorder) {
        int begin = 0;
        int end = postorder.length - 1;
        postIndex = end;
        return createTree(inorder, postorder, begin, end);

    }
    private TreeNode createTree(int[] inorder, int[] postorder, int begin, int end) {
        if(begin > end) return null;
        TreeNode root = new TreeNode(postorder[postIndex]);
        int rootIndex = getRootIndex1(inorder, root.val, begin, end);
        if(rootIndex == -1) return null;

        postIndex--;
        root.right = createTree(inorder, postorder, rootIndex + 1, end);
        root.left = createTree(inorder, postorder, begin, rootIndex - 1);

        return root;
    }
    private int getRootIndex1(int[] inorder, int key, int begin, int end) {
        for(int i = begin; i <= end; i++) {
            if(inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }


    //105. 从前序与中序遍历序列构造二叉树
    private int preIndex;
    public TreeNode buildTree2(int[] preorder, int[] inorder) {
        return buildChildTree2(preorder, inorder, 0, inorder.length-1);

    }

    private TreeNode buildChildTree2(int[] preorder, int[] inorder, int begin, int end) {
        if(begin > end) return null;

        TreeNode root = new TreeNode(preorder[preIndex]);
        int rootIndex = getRootIndex2(inorder, root.val, begin, end);
        preIndex++;

        root.left = buildChildTree2(preorder, inorder, begin, rootIndex - 1);
        root.right = buildChildTree2(preorder, inorder, rootIndex + 1, end);
        return root;
    }
    private int getRootIndex2(int[] inorder, int key, int begin, int end) {
        for(int i = begin; i <= end; i++) {
            if(inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }



    //145. 二叉树的后序遍历(非递归)
    class Solution {
        public List<Integer> postorderTraversal(TreeNode root) {
            //后序非递归遍历
            List<Integer> list = new ArrayList<>();
            if(root == null) return list;

            Stack<TreeNode> stack = new Stack<>();
            TreeNode flag = null;       //用来标记出过栈的结点
            stack.push(root);
            root = root.left;
            while(root != null || !stack.empty()){
                if(root != null) {
                    stack.push(root);
                    root = root.left;
                }else {
                    TreeNode top = stack.peek();
                    if(top.right == null || flag == top.right) {
                        flag = stack.pop();
                        list.add(flag.val);
                    }else {
                        root = top.right;
                    }
                }
            }
            return list;

        }
    }
}


